\section{Функция \IT{abs()} без переходов}
\label{chap:branchless_abs}

Снова вернемся к уже рассмотренному ранее примеру \myref{sec:abs} и спросим себя, возможно ли
сделать версию этого кода под x86 без переходов?

\lstinputlisting[style=customc]{abs.c}

И ответ положительный.

\subsection{\Optimizing GCC 4.9.1 x64}

Мы можем это увидеть если скомпилируем оптимизирующим GCC 4.9:

\lstinputlisting[caption=\Optimizing GCC 4.9 x64,style=customasmx86]{\CURPATH/abs_GCC491_x64_O3_RU.asm}

И вот как он работает:

Арифметически сдвигаем входное значение вправо на 31.

Арифметический сдвиг означает знаковое расширение, так что если \ac{MSB} это 1, то все 32 бита будут
заполнены единицами, либо нулями в противном случае.

\myindex{x86!\Instructions!SAR}
Другими словами, инструкция \TT{SAR REG, 31} делает \TT{0xFFFFFFFF} если знак был отрицательным либо 0 если
положительным.

После исполнения \TT{SAR}, это значение у нас в \EDX.

\myindex{x86!\Instructions!XOR}
Затем, если значение \TT{0xFFFFFFFF} (т.е. знак отрицательный) входное значение инвертируется
(потому что \TT{XOR REG, 0xFFFFFFFF} работает как операция инвертирования всех бит).

Затем, снова, если значение \TT{0xFFFFFFFF} (т.е. знак отрицательный), 1 прибавляется к итоговому результату
(потому что вычитание $-1$ из значения это то же что и инкремент).

Инвертирование всех бит и инкремент, это то, как меняется знак у значения в формате two's complement: 
\myref{sec:signednumbers}.

Мы можем заметить, что последние две инструкции делают что-то если знак входного значения отрицательный.

В противном случае (если знак положительный) они не делают ничего, оставляя входное значение нетронутым.

Алгоритм разъяснен в \InSqBrackets{\HenryWarren 2-4}.
Трудно сказать, как именно GCC сгенерировал его, соптимизировал сам или просто нашел подходящий шаблон среди известных?%

\subsection{\Optimizing GCC 4.9 ARM64}

GCC 4.9 для ARM64 делает почти то же, только использует полные 64-битные регистры.

Здесь меньше инструкций, потому что входное значение может быть сдвинуто используя суффикс инструкции (\q{asr})
вместо отдельной инструкции.

\lstinputlisting[caption=\Optimizing GCC 4.9 ARM64,style=customasmARM]{\CURPATH/abs_GCC49_ARM64_O3_RU.s}

